package base.day04;

/**
 * 描述：
 *      反转单向双向链表
 * @author hl
 * @version 1.0
 * @date 2020/10/26 15:37
 */
public class Code_03_ReverseList {

    /**
     * 定义一个新的头节点，遍历原始链表相当于每次将遍历的节点插入到新的头节点的下一个位置
     * @param head
     */
    public static Node reverseList(Node head){
       Node newHead = new Node(0);
       Node cur = head;
       Node next = null;
       while(cur != null){
           next = cur.next;
           cur.next = newHead.next;
           newHead.next = cur;
           cur = next;
       }
       return newHead.next;
    }

    /**
     * 定义连个指针，分别指向遍历的上一个和下一个节点，原地反转
     * @param head
     * @return
     */
    public static Node reverseList2(Node head){
        Node pre = null;
        Node next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 反转双向链表，每次更新前一个节点和后一个节点
     * @param head
     * @return
     */
    public static DoubleNode reverseList(DoubleNode head){
        DoubleNode next = head.next;
        DoubleNode pre = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }



    public static class Node {
        public int value;
        public Node next;
        public Node(int data) {
            this.value = data;
        }
    }
    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            this.value = data;
        }
    }

    public static void printLinkedList(Node head) {
        System.out.print("Linked List: ");
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void printDoubleLinkedList(DoubleNode head) {
        System.out.print("Double Linked List: ");
        DoubleNode end = null;
        while (head != null) {
            System.out.print(head.value + " ");
            end = head;
            head = head.next;
        }
        System.out.print("| ");
        while (end != null) {
            System.out.print(end.value + " ");
            end = end.last;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        printLinkedList(head1);
        head1 = reverseList(head1);
        printLinkedList(head1);

        DoubleNode head2 = new DoubleNode(1);
        head2.next = new DoubleNode(2);
        head2.next.last = head2;
        head2.next.next = new DoubleNode(3);
        head2.next.next.last = head2.next;
        head2.next.next.next = new DoubleNode(4);
        head2.next.next.next.last = head2.next.next;
        printDoubleLinkedList(head2);
        printDoubleLinkedList(reverseList(head2));

    }
}
